package first_practice;

import java.util.*;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-98-验证二叉搜索树
 * @date 2025/4/11 10:53
 */
//public class Solution98 {
//    public boolean isValidBST(TreeNode root) {
//        // 中序遍历这个二叉树，若遍历的结果严格递增，则该二叉树为二叉搜索树
//        boolean ans = true;
//        List<Integer> val = new ArrayList<>();
//        InOrder(root, val);
//        for (int i = 0; i < val.size() - 1; i++) {
//            int j = i + 1;
//            if (val.get(i) >= val.get(j))
//                return false;
//        }
//        return ans;
//    }
//
//    private void InOrder(TreeNode root, List<Integer> val) {
//        if (root == null)
//            return;
//        InOrder(root.left, val);
//        val.add(root.val);
//        InOrder(root.right, val);
//    }
//}

public class Solution98 {
    public static void main(String[] args) {

    }

    public static boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        double inOrder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                // 将全部左边的节点压入栈中
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val <= inOrder)
                return false;
            inOrder = root.val;
            root = root.right; // 继续压入右边的节点
        }

        return true;
    }
}
